package com.xiaoyg.algorithm;

public class MergeTwoLists {

    public static void main(String[] args) {


        ListNode node3 = new ListNode(4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);

        System.out.println(node1);

        ListNode node13 = new ListNode(4);
        ListNode node12 = new ListNode(3, node13);
        ListNode node11 = new ListNode(1, node12);
        System.out.println(node11);

        ListNode result = mergeTwoLists2(node1,node11);
        System.out.println(result);
    }


    public static ListNode mergeTwoLists(ListNode head1,ListNode head2){
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        ListNode dummery = new ListNode(0);
        ListNode p = dummery;
        while (head1 != null && head2 != null){
            if (head1.val < head2.val){
                p.next = head1;
                head1 = head1.next;
            }else {
                p.next = head2;
                head2 = head2.next;
            }
            p = p.next;
        }
        if (head1 == null){
            p.next = head2;
        }
        if (head2 == null){
            p.next = head1;
        }
        return dummery.next;
    }

    public static ListNode mergeTwoLists2(ListNode head1,ListNode head2){
        if (head1==null) return head2;
        if (head2==null) return head1;

        //递归结束条件
        if (head1.val < head2.val){
            head1.next = mergeTwoLists2(head1.next,head2);
            return head1;
        }
        head2.next = mergeTwoLists2(head1,head2.next);
        return head2;
    }



  static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }

      @Override
      public String toString() {
          return "ListNode{" +
                  "val=" + val +
                  ", next=" + next +
                  '}';
      }
  }

}
